#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _pair_t {
    int v; /* volume */
    int w; /* weight */
} pair_t;

const pair_t pr[] = {
    { 1, 2 },
    { 3, 8 },
    { 28, 96 },
    { 19, 62 },
    { 13, 37 },
    { 7, 23 }
};

const int n = sizeof(pr)/sizeof(pr[0]);
int maxw;
int curr[6];
int result[6]; /* cannot use 'n' here in c code... */

/* unbounded, recursive version. */
/* since input is not sorted, there are duplicate calculations. */
void knapsack1(int i, int allv, int allw)
{
    if (i == n) {
        if (maxw < allw) {
            maxw = allw;
            memcpy(result, curr, sizeof(curr));
        }
        return;
    }
    int j, k;
    for (j = i; j < n; j++) {
        for (k = 0; k*pr[j].v <= allv; k++) {
            curr[j] = k;
            knapsack1(i+1, allv-k*pr[j].v, allw+k*pr[j].w);
        }
    }
}

/* unbounded, recursive + dynamic programming version. */
int knapsack2(int allv, int *prez)
{
    if (prez[allv] >= 0) {
        return prez[allv];
    }
    int j, curr_max = 0;
    for (j = 0; j < n; j++) {
        if (allv >= pr[j].v) {
            int w = knapsack2(allv-pr[j].v, prez) + pr[j].w;
            if (curr_max < w) {
                curr_max = w;
            }
        }
    }
    prez[allv] = curr_max;
    return curr_max;
}

/* unbounded, dynamic programming version. */
int knapsack3(int allv, int *prez)
{
    int i, j;
    for (i = 1; i <= allv; i++) {
        int curr_max = 0;
        for (j = 0; j < n; j++) {
            if (i >= pr[j].v) {
                if (curr_max < prez[i-pr[j].v] + pr[j].w) {
                    curr_max = prez[i-pr[j].v] + pr[j].w;
                }
            }
        }
        prez[i] = curr_max;
    }
    return prez[allv];
}

/* 0-1, recursive version. */
void knapsack4(int i, int allv, int allw)
{
    if (i == n) {
        if (maxw < allw) {
            maxw = allw;
            memcpy(result, curr, sizeof(curr));
        }
        return;
    }
    curr[i] = 0;
    knapsack4(i+1, allv, allw);
    if (allv >= pr[i].v) {
        curr[i] = 1;
        knapsack4(i+1, allv-pr[i].v, allw+pr[i].w);
    }
}

/* 0-1, dynamic programming version. */
int knapsack5(int allv, int *prez)
{
#if 0
    int i, j;
    for (i = 0; i < n; i++) {
        for (j = allv; j >= 0; j--) {
            if (j >= pr[i].v) {
                if (prez[j] < prez[j-pr[i].v] + pr[i].w) {
                    prez[j] = prez[j-pr[i].v] + pr[i].w;
                }
            }
        }
    }
    return prez[allv];
#else
    int i, j, max;
    int size = (n+1) * (allv+1) * sizeof(int);
    int *allprez = malloc(size);
    memset(allprez, 0, size);
    for (i = 0; i < n; i++) {
        for (j = 0; j <= allv; j++) {
            int *curr = allprez + (i+1)*(allv+1) + j; /* int *curr = &allprez[i+1][j]; */
            int *prev = curr - (allv+1); /* int *prev = &allprez[i][j] */
            *curr = *prev;
            if (j >= pr[i].v) {
                prev = prev - pr[i].v; /* prev = &allprez[i][j-pr[i].v] */
                if (*curr < (*prev + pr[i].w)) {
                    *curr = (*prev + pr[i].w);
                }
            }
        }
    }
    max = *(allprez + n*(allv+1) + allv); /* max = allprez[n][allv]; */
    memcpy(prez, allprez + n*(allv+1), (allv+1)*sizeof(int));
    free(allprez);
    return max;
#endif
}

void print_answer(int *prez, int maxv, int maxw)
{
    int i;
    memset(result, 0, sizeof(result));
    while (maxv) {
        while (maxv > 0 && prez[maxv] == prez[maxv-1]) {
            maxv--;
        }
        for (i = 0; i < n; i++) {
            if (maxv >= pr[i].v &&  prez[maxv] - prez[maxv-pr[i].v] == pr[i].w) {
                maxv = maxv - pr[i].v;
                maxw = prez[maxv];
                result[i]++;
                break;
            }
        }
    }
    for (i = 0; i < n; i++) {
        printf("[%d,%d] * %d\n", pr[i].v, pr[i].w, result[i]);
    }
}

int main()
{
    const int allv = 148;
    const int allv2 = 46;
    int i;
    /* test1 */
    printf("=== test1: unbounded, recursive version ===\n");
    maxw = 0;
    memset(curr, 0, sizeof(curr));
    memset(result, 0, sizeof(result));
    knapsack1(0, allv, 0);
    printf("max weight = %d\n", maxw);
    for (i = 0; i < n; i++) {
        printf("[%d,%d] * %d\n", pr[i].v, pr[i].w, result[i]);
    }
    /* test2 */
    printf("=== test2: unbounded, recursive + dynamic programming version ===\n");
    int prez[allv+1];
    memset(prez, -1, sizeof(prez)); /* -1 to mark not visited */
    maxw = knapsack2(allv, prez);
    printf("max weight = %d\n", maxw);
    print_answer(prez, allv, maxw);
    /* test3 */
    printf("=== test3: unbounded, dynamic programming version ===\n");
    memset(prez, 0, sizeof(prez));
    maxw = knapsack3(allv, prez);
    printf("max weight = %d\n", maxw);
    print_answer(prez, allv, maxw);
    /* test4 */
    printf("=== test4: 0-1, recursive version ===\n");
    maxw = 0;
    memset(curr, 0, sizeof(curr));
    memset(result, 0, sizeof(result));
    knapsack4(0, allv2, 0);
    printf("max weight = %d\n", maxw);
    for (i = 0; i < n; i++) {
        printf("[%d,%d] * %d\n", pr[i].v, pr[i].w, result[i]);
    }
    /* test5 */
    printf("=== test5: 0-1, dynamic programming version ===\n");
    int prez2[allv2+1];
    memset(prez2, 0, sizeof(prez2));
    maxw = knapsack5(allv2, prez2);
    printf("max weight = %d\n", maxw);
    print_answer(prez2, allv2, maxw);
    return 0;
}
